import java.util.HashMap;
import java.util.Map;

public class MapSet {
    public class Node{
        int val;
        Node next;
        Node random;
        public Node(int val){
            this.val = val;
        }
    }
    Node head;
    public Node create(){
        Node A = new Node(1);
        Node B = new Node(2);
        Node C = new Node(3);
        Node D = new Node(4);
        Node E = new Node(5);
        A.next = B;
        B.next = C;
        C.next = D;
        D.next = E;
        E.next = null;
        A.random = B;
        B.random = B;
        C.random = E;
        D.random = A;
        E.random = null;
        head = A;
        return head;
    }
    public Node deepCopy(){
        if (head == null) return null;
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null){
            Node newNode = new Node(cur.val);
            map.put(cur,newNode);
            cur = cur.next;
        }
        cur = head;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}
